//二进制读写来源：http://c.biancheng.net/cpp/biancheng/view/260.html
#include <fstream>
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include <iostream>
#include <time.h>
#include <math.h>
using namespace std;

 //#define   RAND_MAX   0x7fffu    
 //这个是bcc55中的定义，说明这个整数的最大数是0x7fffu，u代表unicode编码。
#define random(x) (int)(((double)rand()/RAND_MAX)*pow(10,rand()%x))

struct Recode
{
	int A;//4byte
	char B[12];//12byte
};
int main()
{
    cout<<"-------TPMMS Running-----"<<endl;
    srand((unsigned)time(0));
    int a;
    fstream iofile("Recode.dat", ios::in | ios::out | ios::binary);
    fstream resultfile("Result.dat", ios::in | ios::out | ios::binary);
    fstream fr("fresult.dat", ios::in | ios::out | ios::binary);
    if (!iofile)
	{
	    cerr << "open error!" << endl;
		abort();
	}
    srand(time(NULL));
    for (int m = 0; m < 1000; m++)
    {
        Recode recode[1000]={};
        for (int n = 0; n < 1000; n++)
        {
            a=rand()%1000000;
            Recode r={a,"abc"};
            recode[n]=r;
        }
        for (int i = 0; i<1000; i++)
		{
            iofile.write((char *)&recode[i], sizeof(recode[i]));
        }
        
    }
    //Recode recode[20];
    //for (int i = 0; i < 20000; i=i+1000)
    //{
        //iofile.seekg(i*sizeof(recode[i]), ios::beg);  
		//iofile.read((char *)&recode[i / 1000], sizeof(recode[0]));
        //cout<<recode[i/1000].A<<endl;
        //cout<<recode[i/1000].B<<endl;
    //}
    
    //1M内存内部排序，对应65536个记录,256个磁盘块,1个子集合
    //先排前15个子集合，每个集合有65535个记录
    for (int i = 0; i < 15; i++)
    {
        cout<<"wccccccc"<<endl;
        Recode inter_recode[65535];
        for (int k = i*65535; k < i*65535+65535; k++)
        {
            iofile.seekg(k*sizeof(inter_recode[0]), ios::beg);
            iofile.read((char *)&inter_recode[k%65535], sizeof(inter_recode[0]));
        }
        //冒泡排序
        for (int o = 0; o < 65534; o++)
        {
            for (int p = 65534; p >o; p--)
            {
                if (inter_recode[p-1].A>inter_recode[p].A)
                {
                    int temp;
                    temp=inter_recode[p-1].A;
                    inter_recode[p-1].A=inter_recode[p].A;
                    inter_recode[p].A=temp;
                }
            }
        }
        //将子集合写回到磁盘中
        for (int k = i*65535; k < i*65535+65535; k++)
        {
            resultfile.seekp(k*sizeof(inter_recode[0]), ios::beg);
            resultfile.write((char *)&inter_recode[k%65535], sizeof(inter_recode[0]));
        }
    }
    //最后一个子集合（第16个子集合）
    Recode inter_recode[65535];
    for (int k = 983025; k < 1000000; k++)
    {
        iofile.seekg(k*sizeof(inter_recode[0]), ios::beg);
        iofile.read((char *)&inter_recode[k%65535], sizeof(inter_recode[0]));
    }
    cout<<"16.1"<<endl;
    //冒泡排序
    for (int o = 0; o < 16974; o++)
    {
        for (int p = 16974; p >o; p--)
        {
            if (inter_recode[p-1].A>inter_recode[p].A)
            {
                int temp;
                temp=inter_recode[p-1].A;
                inter_recode[p-1].A=inter_recode[p].A;
                inter_recode[p].A=temp;
            }
        }
    }
    cout<<"16.2"<<endl;
    //将子集合写回到磁盘中
    for (int k = 983025; k < 1000000; k++)
    {
        resultfile.seekp(k*sizeof(inter_recode[0]), ios::beg);
        resultfile.write((char *)&inter_recode[k%65535], sizeof(inter_recode[0]));
    }
    cout<<"wcl"<<endl;
        //1M内存,256个磁盘块,16路归并
    Recode r1[256];
    Recode r2[256];
    Recode r3[256];
    Recode r4[256];
    Recode r5[256];
    Recode r6[256];
    Recode r7[256];
    Recode r8[256];
    Recode r9[256];
    Recode r10[256];
    Recode r11[256];
    Recode r12[256];
    Recode r13[256];
    Recode r14[256];
    Recode r15[256];
    Recode r16[256];
    Recode r17[256];
    int m[17]={0};//记录r%d数组排到第几位了，到了256就要换新的或者输出
    int io[16]={0};//记录在1000000中的索引
    int findex=0;
    int M=65535;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg(i*sizeof(r1[0]), ios::beg);
        resultfile.read((char *)&r1[i], sizeof(r1[0]));
    }
    io[0]=255;//读了256个记录，对应索引为255
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M+i)*sizeof(r2[0]), ios::beg);
        resultfile.read((char *)&r2[i], sizeof(r2[0]));
    }
    io[1]=M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*2+i)*sizeof(r3[0]), ios::beg);
        resultfile.read((char *)&r3[i], sizeof(r3[0]));
    }
    io[2]=2*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*3+i)*sizeof(r4[0]), ios::beg);
        resultfile.read((char *)&r4[i], sizeof(r4[0]));
    }
    io[3]=3*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*4+i)*sizeof(r5[0]), ios::beg);
        resultfile.read((char *)&r5[i], sizeof(r5[0]));
    }
    io[4]=4*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*5+i)*sizeof(r6[0]), ios::beg);
        resultfile.read((char *)&r6[i], sizeof(r6[0]));
    }
    io[5]=5*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*6+i)*sizeof(r7[0]), ios::beg);
        resultfile.read((char *)&r7[i], sizeof(r7[0]));
    }
    io[6]=6*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*7+i)*sizeof(r8[0]), ios::beg);
        resultfile.read((char *)&r8[i], sizeof(r8[0]));
    }
    io[7]=7*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*8+i)*sizeof(r9[0]), ios::beg);
        resultfile.read((char *)&r9[i], sizeof(r9[0]));
    }
    io[8]=8*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*9+i)*sizeof(r10[0]), ios::beg);
        resultfile.read((char *)&r10[i], sizeof(r10[0]));
    }
    io[9]=9*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*10+i)*sizeof(r11[0]), ios::beg);
        resultfile.read((char *)&r11[i], sizeof(r11[0]));
    }
    io[10]=10*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*11+i)*sizeof(r12[0]), ios::beg);
        resultfile.read((char *)&r12[i], sizeof(r12[0]));
    }
    io[11]=11*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*12+i)*sizeof(r13[0]), ios::beg);
        resultfile.read((char *)&r13[i], sizeof(r13[0]));
    }
    io[12]=12*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*13+i)*sizeof(r14[0]), ios::beg);
        resultfile.read((char *)&r14[i], sizeof(r14[0]));
    }
    io[13]=13*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*14+i)*sizeof(r15[0]), ios::beg);
        resultfile.read((char *)&r15[i], sizeof(r15[0]));
    }
    io[14]=14*M+255;
    for (int i = 0; i < 256; i++)
    {
        resultfile.seekg((M*15+i)*sizeof(r16[0]), ios::beg);
        resultfile.read((char *)&r16[i], sizeof(r16[0]));
    }
    io[15]=15*M+255;
    cout<<"dyc"<<endl;
    //每次遍历16个数组选出最小的，把最小的加到r17中，然后对应的数组记录++，判断是否满了或空了
    bool flag=false;
    bool f1=true,f2=true,f3=true,f4=true,f5=true,f6=true,f7=true,f8=true,f9=true,f10=true,f11=true,f12=true,f13=true,f14=true,f15=true,f16=true;
    while(!flag)
    {
        int min=1000000;
        int index=-1;
        if(r1[m[0]].A<min)
        {
            min=r1[m[0]].A;
            index=1;
        }
        if(r2[m[1]].A<min)
        {
            min=r2[m[1]].A;
            index=2;
        }
        if(r3[m[2]].A<min)
        {
            min=r3[m[2]].A;
            index=3;
        }
        if(r4[m[3]].A<min)
        {
            min=r4[m[3]].A;
            index=4;
        }
        if(r5[m[4]].A<min)
        {
            min=r5[m[4]].A;
            index=5;
        }
        if(r6[m[5]].A<min)
        {
            min=r6[m[5]].A;
            index=6;
        }
        if(r7[m[6]].A<min)
        {
            min=r7[m[6]].A;
            index=7;
        }
        if(r8[m[7]].A<min)
        {
            min=r8[m[7]].A;
            index=8;
        }
        if(r9[m[8]].A<min)
        {
            min=r9[m[8]].A;
            index=9;
        }
        if(r10[m[9]].A<min)
        {
            min=r10[m[9]].A;
            index=10;
        }
        if(r11[m[10]].A<min)
        {
            min=r11[m[10]].A;
            index=11;
        }
        if(r12[m[11]].A<min)
        {
            min=r12[m[11]].A;
            index=12;
        }
        if(r13[m[12]].A<min)
        {
            min=r13[m[12]].A;
            index=13;
        }
        if(r14[m[13]].A<min)
        {
            min=r14[m[13]].A;
            index=14;
        }
        if(r15[m[14]].A<min)
        {
            min=r15[m[14]].A;
            index=15;
        }
        if(r16[m[15]].A<min)
        {
            min=r16[m[15]].A;
            index=16;
        }
        Recode rr={min,"abc"};
        if (index!=-1)
        {
            r17[m[16]]=rr;
            m[16]=m[16]+1;
        }
        if (m[16]==256)
        {
            for (int f = 0; f < 256; f++)
            {
                fr.seekp((findex+f)*sizeof(r17[0]), ios::beg);
                fr.write((char *)&r17[f], sizeof(r17[0]));
            }
            findex=findex+256;
            //cout<<findex<<endl;
            m[16]=0;
            if (findex>=1000000)
            {
                flag=true;
            }
            
        }
        if (index==-1)
        {
            for (int f = 0; f < m[16]; f++)
            {
                fr.seekp((findex+f)*sizeof(r17[0]), ios::beg);
                fr.write((char *)&r17[f], sizeof(r17[0]));
            }
            iofile.close();
            resultfile.close();
            fr.close();
            return 0;
            
        }
        

        if (index!=-1)
        {
            m[index-1]=m[index-1]+1;
            if (m[index-1]==256)
            {
                Recode rr={100000000,"abc"};
                if (index==1&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[0]+n)*sizeof(r1[0]), ios::beg);
                           resultfile.read((char *)&r1[n], sizeof(r1[0]));
                        }
                        r1[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[0]+n)*sizeof(r1[0]), ios::beg);
                           resultfile.read((char *)&r1[n], sizeof(r1[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==2&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r2[0]), ios::beg);
                           resultfile.read((char *)&r2[n], sizeof(r2[0]));
                        }
                        r2[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r2[0]), ios::beg);
                           resultfile.read((char *)&r2[n], sizeof(r2[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==3&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r3[0]), ios::beg);
                           resultfile.read((char *)&r3[n], sizeof(r3[0]));
                        }
                        r3[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r3[0]), ios::beg);
                           resultfile.read((char *)&r3[n], sizeof(r3[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==4&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r4[0]), ios::beg);
                           resultfile.read((char *)&r4[n], sizeof(r4[0]));
                        }
                        r4[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r4[0]), ios::beg);
                           resultfile.read((char *)&r4[n], sizeof(r4[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==5&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r5[0]), ios::beg);
                           resultfile.read((char *)&r5[n], sizeof(r5[0]));
                        }
                        r5[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r5[0]), ios::beg);
                           resultfile.read((char *)&r5[n], sizeof(r5[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==6&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r6[0]), ios::beg);
                           resultfile.read((char *)&r6[n], sizeof(r6[0]));
                        }
                        r6[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r6[0]), ios::beg);
                           resultfile.read((char *)&r6[n], sizeof(r6[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==7&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r7[0]), ios::beg);
                           resultfile.read((char *)&r7[n], sizeof(r7[0]));
                        }
                        r7[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r7[0]), ios::beg);
                           resultfile.read((char *)&r7[n], sizeof(r7[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==8&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r8[0]), ios::beg);
                           resultfile.read((char *)&r8[n], sizeof(r8[0]));
                        }
                        r8[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r8[0]), ios::beg);
                           resultfile.read((char *)&r8[n], sizeof(r8[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==9&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r9[0]), ios::beg);
                           resultfile.read((char *)&r9[n], sizeof(r9[0]));
                        }
                        r9[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r9[0]), ios::beg);
                           resultfile.read((char *)&r9[n], sizeof(r9[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==10&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r10[0]), ios::beg);
                           resultfile.read((char *)&r10[n], sizeof(r10[0]));
                        }
                        r10[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r10[0]), ios::beg);
                           resultfile.read((char *)&r10[n], sizeof(r10[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==11&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r11[0]), ios::beg);
                           resultfile.read((char *)&r10[n], sizeof(r11[0]));
                        }
                        r11[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r11[0]), ios::beg);
                           resultfile.read((char *)&r11[n], sizeof(r11[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==12&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r12[0]), ios::beg);
                           resultfile.read((char *)&r12[n], sizeof(r12[0]));
                        }
                        r12[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r12[0]), ios::beg);
                           resultfile.read((char *)&r12[n], sizeof(r12[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==13&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r13[0]), ios::beg);
                           resultfile.read((char *)&r13[n], sizeof(r13[0]));
                        }
                        r13[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r13[0]), ios::beg);
                           resultfile.read((char *)&r13[n], sizeof(r13[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==14&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r14[0]), ios::beg);
                           resultfile.read((char *)&r14[n], sizeof(r14[0]));
                        }
                        r14[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r14[0]), ios::beg);
                           resultfile.read((char *)&r14[n], sizeof(r14[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==15&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>index*M-1-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < index*M-1; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r15[0]), ios::beg);
                           resultfile.read((char *)&r15[n], sizeof(r15[0]));
                        }
                        r15[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r15[0]), ios::beg);
                           resultfile.read((char *)&r15[n], sizeof(r15[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                if (index==16&&io[index-1]<index*M-1)
                {
                    if (io[index-1]>1000000-260)
                    {
                        int n;
                        for ( n = 0; io[index-1] < 1000000; io[index-1]++,n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r16[0]), ios::beg);
                           resultfile.read((char *)&r16[n], sizeof(r16[0]));
                        }
                        r16[n]=rr;
                        io[index-1]=index*M-1;
                    }
                    else
                    {
                        for (int n = 0; n < 256; n++)
                        {
                           resultfile.seekg((1+io[index-1]+n)*sizeof(r16[0]), ios::beg);
                           resultfile.read((char *)&r16[n], sizeof(r16[0]));
                        }
                        io[index-1]=io[index-1]+256;
                    }
                }
                m[index-1]=0;
            }
            
        }
        
        
    }
    cout<<"--------TPMMS FINISH------------"<<endl;
}
